package com.LeeCode;

import java.util.HashSet;
import java.util.Set;

/**
 * 和为目标值且不重叠的非空子数组的最大数目
 */

public class Code1546 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 1, 1};
        int target = 2;
        System.out.println(new Code1546().maxNonOverlapping(nums, target));
    }

    public int maxNonOverlapping(int[] nums, int target) {
        int count = 0, preSum = 0;
        Set<Integer> set = new HashSet<>();
        set.add(0);
        for (int num : nums) {
            preSum += num;
            if (set.contains(preSum - target)) {
                count++;
                set.clear();
                set.add(0);
                preSum = 0;
            } else {
                set.add(preSum);
            }
        }

        return count;
    }
}
